ABSTRACT:
In the emerging world of mobile technology with 3G mobile computing systems, it is of evident importance for a cellular network to link, locate, update and generate query result for mobile clients in reduced time and cost. Earlier, two-tier architecture design is used and adopted for locating such clients. With the limitation of non-scalability of two-tier architecture, a hierarchical database tree like structure is proposed to organize information in location databases of cellular mobile computing system. Furthermore, the leaf nodes are designated as disjoint sets of the whole location database having information related to the client residing in each cell. A cell can be allocated to a mobile client with the help of their HLR (Home Location Register). At each instance of a client crossing its cell boundary needs to link, locate, and updating their VLR (Visitor Location Register) location database. Producing query results for such mobile clients involves heavy overheads with the increased burden on the total database management cost especially in a hierarchical distributed database with the increased mobility factor of a client. The first part of the research paper discusses about the problem faced by such static and non-scalable architecture of cellular mobile computing systems. The second part of the paper focuses upon a heuristic algorithm based on set covering problem, used with the objective of calculating the optimal distance threshold between two-clustered cells. Thus, the mobility pattern of a client is generated over a time, which helps in reducing the time and cost factor.
KEYWORDS: Mobile Client, Location Database, Mobility Matrix Transformation, Base Station Clustering.
INTRODUCTION:
In the recent times, mobile computing has received a great importance. Mobile computing technology is emerging in the area of real time systems like location management, navigation system and monitoring system. A cellular network is generally divided among various disjoint cells, which are mutually exclusive. Each mobile user is provided a base station, which is combined to create an imaginary cell boundary. A GSM network keeps track of client's mobility. A base station is responsible for managing data of such real-time applications of clients. In an existing system, two-tier architecture is used to manage clients connected to Message Switching center (MSC). A MSC keeps a detailed record of client's profile, location, maintainability of Home Location register (HLR) and Visitor Location Register (VLR). Thus a mobility pattern of each user is defined. In the event of movement of a mobile client, its HLR is updated. In order to search a mobile client, the respective VLR is searched first and in case of not finding the correct data then HLR is searched.
The broadcast of polling messages for communication with the client is done to ensure that it is the right call where the client is now residing. Two-tier architecture is simple to implement but faces limitations like non-scalability and its continuous association with HLR. Maintaining such association of mobile client users with its HLR takes much cost and larger data base storage space. Implementing hierarchical database structure instead of two-tier architecture increases the speed of searching operation. The cost for locating a mobile client highly depends on the locations of the calling mobile client and the called mobile client. If the called mobile client is far away from the HLR, the cost for locating such client could be very expensive. At the same time different mobile clients will have different mobility pattern and their mobility pattern may change gradually with the passage of time. Therefore, a static hierarchical location database structure may not be able to meet the requirements in minimizing the location management cost. The researchers have suggested various types of location management schemes in the last few years [See References]. We enumerate below some of the fundamental types of schemes that have been proposed in literature.
a) Paging of a single cell can be used to locate, update user’s information, if its exact cell location is known.
b) Broadcasting polling messages option can be used, in order to perform paging of the system area. But as a result it will consume whole bandwidth.
c) A more efficient scheme3,9 will keep track of a location area, consisting of cluster of cells, where the mobile user might be found, and use the paging scheme simultaneously in all the cells within that area. The aim is to minimize the total overhead in locating a user that comprises both the signaling overhead in paging the cells and the overhead due to the updating the user locality.
d) An optimal value of the size of location area for the user is computed based on minimizing the cost function, comprising of paging and updating cost components3.
e) Another approach 10 uses past history movements to create different partitioned cell for various users and the changes takes place only when the user changes its mobility pattern by the passage of time.
f) Another approach partitions the location area into disjoint sets of cells based on a user profile, which is generally a history of user’s movements called partitions. Each user will be allocated a set of partitions of cells. The updating will take place only when the user changes partition.
In this paper we study the location update problem in static hierarchical location database structure. Our objective is to minimize the total location management cost with the help of effective method proposed to re-organize the location management database.
The rest of the paper is organized as follows. A distributed database approach is discussed for locating mobile clients in Section 2. Basic terminology and parameters are classified in Section 3. Section 4 covers the re-organization of the location database. It includes the procedure determining the mobility matrix. Section 5 is the conclusion and future work.
Figure 1. Distributed database structure for locating mobile clients maintained by cellular network.
The whole 3G cellular networks are distributed between various MSC's at base locations as shown in fig1. This way the whole network is connected in number of disjoint cells at the leaf node of a tree like hierarchical database structure. The main advantage of such partitioning is utilizing the limited bandwidth of available channel. Large numbers of clients are managed by MSC's. Clients generally make calls or submit query to other mobile clients. Furthermore, it is observed that a mobile client calls to a certain group over a period. Thus, each of them has their own unique patterns, which is prone to changes in future. It is of vital importance that the location updates of a client is to be done, if the same client crosses its boundary. The two parameters for generation of mobility pattern of a client are (1) the frequency of movement and (2) its moving distance.
In this section, we will discuss the method proposed for calculating optimal distance threshold for the distance- based update method such that the total location management cost can be minimized. In case of a movement of mobile client from its previous cell to another cell, an update will be generated for its location databases of its present cell. Now if the distance is greater than the pre-defined threshold then an update is made otherwise no update is performed. In hierarchical structure calculating the distance between two cells is easy and the table in the form of matrix is generated which is static in nature. However, calculating the optimal distance threshold is not an easy task. An optimal distance threshold can neither be small because of the frequent updation requirement nor can it be large because it will increase the uncertainty in locating mobile clients.
BASIC TERMINOLOGY:
The basic definition used for the above-discussed method needs to consider two parameters i.e. update cost and paging cost. Another major factor affecting the total cost to update is call mobility ratio (CMR) [2]. The CMR must be high enough to reduce the overall cost significantly. Here it is proposed that the least common ancestor in a hierarchical database structure’s base stations BSi and BSj distant from each other can be termed as LCA(BSi, BSj) [1].
Dist( i,j )= lca( BS(i), BS(j) )
Current BS: Let P be the mobile client.
Distance between two clients p and q:
Dist( previous_BS(p),current_BS(q) )
The following look up procedure needs to relate with the cost estimation. The total cost includes the cost of broadcasting polling messages (F), the cost for linking up the required location database (L), the cost of database update (U), the cost of query (Q) and finally the cost of polling (P) for a specific client in a cell's base station. An example of searching and updating the desired client can be explained as follows. In case of a mobile client p, residing in BS6 moves to another BS7. To locate the existing client, the updation in the current BS is done and the whole tree is traversed back to the previous location BS to eliminate the entry of the same mobile client The updation entry of the new mobile client is done at all the nodes in the hierarchical tree structure. The entries may be deleted from BS6 to BS0 and the new entries must be made to all the nodes from BS0 to BS7.
The main advantage of this method is the calculation of nearly optimal distance threshold, which is simple to implement. The distance threshold is defined based on the system parameters and how clients move. A new threshold is maintained each time a client crosses its boundary. A matrix representation is suitable for storing the symmetric distance for each adjacent cell.
Figure2: A Mobile system consisting of 9 Base Station.
The locating cost of a mobile client is directly proportional to the distance between the starting and destination cells. The arrangement of hierarchical structure and mobile computing system is totally different. The topology of cells neighboring in the mobile computing is different from its hierarchical structure. For example BS6 and BS9 in mobile computing system is appears to be adjacent to each other although the distance between them in the hierarchical structure is 2. The hierarchical structure of the location databases can have a significant impact on the location management cost. Before constructing the location databases tree, we should consider the mobility patterns of the mobile clients to better optimize the total location management cost. However, the mobility patterns of mobile clients are not static and may change over time so that the location update cost may only augment gradually. The restructuring of location databases should happen whenever it is necessary to reduce the total location update cost.
A location reorganization strategy is used with the objective to reduce the total update cost based on the mobility patterns of the clients. Mobility matrix is maintained to count the no. of border crossings between any two cells to track the mobility matrix. A mobility matrix namely Aij is increased by one. In case of a total location management cost is too high, the location databases are restructured based on the mobility matrix. The re-organization of the mobility matrix is done whenever the total management cost goes high. The rearrangement is done in a manner that with the large number of border crossings between any two nodes is assigned the same sub tree thus decreasing the cost.
The parameters required re-allocating the matrix to reduce the total link, locate and update costs are:
a) Transformation of Mobility Matrix
b) Clustering of Base Station.
c) Re-organization of hierarchical Structure.
Table 1: An Illustration of mobility matrix as per database shown in Figure 1.
|
|
BS1 |
BS2 |
BS3 |
BS4 |
BS5 |
BS6 |
BS7 |
BS8 |
BS9 |
|
BS1 |
C |
100 |
0 |
30 |
25 |
0 |
0 |
0 |
0 |
|
BS2 |
100 |
C |
80 |
40 |
20 |
30 |
0 |
0 |
0 |
|
BS3 |
0 |
80 |
C |
0 |
10 |
30 |
0 |
0 |
0 |
|
BS4 |
30 |
40 |
0 |
C |
120 |
0 |
80 |
25 |
0 |
|
BS5 |
25 |
20 |
10 |
120 |
C |
15 |
160 |
30 |
50 |
|
BS6 |
0 |
30 |
30 |
0 |
15 |
C |
0 |
100 |
60 |
|
BS7 |
0 |
0 |
0 |
80 |
160 |
0 |
C |
40 |
0 |
|
BS8 |
0 |
0 |
0 |
25 |
30 |
100 |
40 |
C |
75 |
|
BS9 |
0 |
0 |
0 |
0 |
50 |
60 |
0 |
75 |
C |
The clustering of the location databases can be formed on the basis of the frequent movement of mobile clients from one base station to another. For example we can assume that a client frequently moves among base station 4, 5 and 7. In the matrix BS 4 and BS5 forms a cluster but does not optimize the cost further.
Table2: Mobility Matrix Transformation.
|
|
BS1 |
BS2 |
BS3 |
BS4 |
BS5 |
BS7 |
BS8 |
BS9 |
BS6 |
|
BS1 |
C |
100 |
0 |
30 |
25 |
0 |
0 |
0 |
0 |
|
BS2 |
100 |
C |
80 |
40 |
20 |
0 |
0 |
0 |
30 |
|
BS3 |
0 |
80 |
C |
0 |
10 |
0 |
0 |
0 |
30 |
|
BS4 |
30 |
40 |
0 |
C |
120 |
80 |
25 |
0 |
0 |
|
BS5 |
20 |
20 |
10 |
120 |
C |
160 |
30 |
50 |
15 |
|
BS7 |
0 |
0 |
0 |
80 |
160 |
C |
40 |
0 |
0 |
|
BS8 |
0 |
0 |
0 |
25 |
30 |
40 |
C |
75 |
100 |
|
BS9 |
0 |
0 |
0 |
0 |
50 |
0 |
75 |
C |
60 |
|
BS6 |
0 |
30 |
30 |
0 |
15 |
0 |
100 |
60 |
C |
The mobility matrix in table 1 is consisting of 9 cells. The number of border crossing is between corresponding cell is indicated as BS 4,5 = 120. The value indicates the number of boundary crossings between base station 4 and base station 5. It is also observe that there large number of boundary crossing between BS4, BS5 as compared to BS1 and BS5. The clustering can be done on the basis of the number of border crossing between them. An optimal method proposed defines the mobility affinity of cells (MAC).
N N
MAC = Σ Σ Aij X ( Ai,j – 1 + Ai, j + 1 + Ai – 1, j + Ai +1,j )
i=1 j=1
where A 0 , j = A i , 0 = A n+1 , j = Ai , n+1 = 0
The best way to group BS cell is to exchange the rows and column of the matrix to calculate MAC for different arrangement of cells. A mobility matrix of N columns will have N! combination of leaf location base stations to choose from. Thus, one can choose the matrix with the greatest value of MAC for clustering1.
Mobility matrix transformation based on the mobility pattern of the clients, is now partitioned in four segments i.e. Upper left (UL), Upper Right (UR), Lower Right (LR), and Lower Left (LL). UL includes as many as base station possible with the values less than optimal threshold range (pre-defined). All databases responsible for the cells in LR have to be larger than the optimal threshold range. This procedure of clustering the same valued BS keeps on until all the location databases in LR
Is less than the pre-defined threshold value. Reorganization procedure of the hierarchical structure is done over the period of time, if and only if the ratio of the total distance of the border crossings over the time is greater that a pre-defined threshold.
Algorithm 1:
Input: Compute Mobility Matrix of a client based on distance.
Output: Reorganized Hierarchical structure.
Step1: Transform mobility matrix M for a time interval.
Step2: Partition the matrix into two parts comprising of UL and LR.
Step3: If (Volume of the location database < Pre-defined Threshold) then
{
Form Cluster
}
Else
{
M = LR;
GOTO Step 2;
}
Step4: The location Database is responsible for the base station in LR
Step5: Form Cluster of the remaining.
The necessity to maintain and update the hierarchical location database of mobile client is growing with the increased number of users for any cellular network. Heavy cost is incurred to maintain such clustered databases with the increased mobility pattern of clients. Now, if the real time location database is not handled properly then the total cost of managing such distributed databases goes very high. A heuristic algorithm is discussed here which helps in cost reduction and time management in locating clients. This research paper exhibits a key solution to this problem as compared to the research work done earlier.
An ideal hierarchical database of a cellular network discussed in this research paper is static in nature, as well as the cells in such databases are at leaf node level which forms a non scalable tree like structure. Now a mobility pattern discovered for a particular client on the basis of distance based method stands invalid, in case of any random change over a passage of time. In such incident a location database's organization approach must accommodate for re-organization of cells for varying mobility pattern with the passage of time. The future implementation should allow adaptability to the areas discussed above, so that the real-time location management cost reduces further.
1. Chen Jixiong, Li Guohui, Xu Huajie, Cia Xia, Yang Bing, “ Location database clustering to Achieve location management time cost reduction in a mobile computing system”, IEEE 0-7803-9335-X/05, 2005.
2. Evaggelia Pitoura and George Samaras, “Locating Objects in Mobile Computing”, IEEE Transactions on Knowledge and Data Engineering,VOL. 13, NO.4, 2001
3. Sajak K. Das and Sanjoy K. Sen, “Adaptive Location Prediction Strategies Based On a Hierarchical Network Model in a Cellular Mobile Environment”, The Computer Journal, vol. 42, no.6, 1999.
4. Xie, H., Tabbane, S. and Goodman, D., “Dynamic Location Area Management and Performance Analysis”, in Proceeding of 43rd IEEE Vehicular Technology Conference, May 1993.
5. Plassmann, D., “Location Management Strategies for Mobile Cellular Networks of 3rd Generation”, in Proceedings of 44th IEEE Vehicular Technology Conf., June 1994.
6. Hüseyin Gökmen Gök and Özgür Ulusoy, “Transmission of Continuous Query Results in Mobile Computing Systems”, Information Sciences, vol. 125, no. 1-4, pages 37-63, 2000.
7. M. Mouly and M.B. Pautet, The GSM System for Mobile Communication, Cell and Sys, 1992.
8. E. Pitoura and I. Fudos, “An Efficient Hierarchical Scheme for Locating Highly Mobile Users”, in Proceedings of the 6th ACM International Conference on Information and Knowledge Management (CIKM98), November 1998, pp 218-225.
9. R. Thomas, H. Gilbert, G. Maziotto, “Influence of the moving of the mobile stations on the performance of a radio mobile cellular network”, Proc. of the Third Nordic Seminar on Digital Land Mobile Radio Communications, sept. 1988
10. B. R. Badrinath, T. Imielinski, A. Virmani, “Locating strategies for personnel communication networks”, Workshop on Networking of personnel communications Appliance, Dec, 1992.
Received on 11.03.2011 Accepted on 22.03.2011
© EnggResearch.net All Right Reserved
Int. J. Tech. 1(1): Jan.-June. 2011; Page 01-04